package com.zjw.algorithm.ready1;

import com.zjw.algorithm.utils.TreeNode;

public class _前序中序构建二叉树 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        return buildTreeInner(preorder, inorder, 0, 0, inorder.length - 1);
    }

    private TreeNode buildTreeInner(int[] preorder, int[] inorder, int preLeft, int inLeft, int inRight) {
        if (inLeft > inRight) {
            return null;
        }
        int root = preorder[preLeft];

        int p = inLeft;
        while (inorder[p] != root) {
            p++;
        }
        int len = p - inLeft + 1;

        TreeNode treeNode = new TreeNode(root);
        treeNode.left = buildTreeInner(preorder, inorder, preLeft + 1, inLeft, p - 1);
        treeNode.right = buildTreeInner(preorder, inorder, preLeft + len, p + 1, inRight);
        return treeNode;
    }
}
